class GraphDict:
    def __init__(self, num, directed=True):
        self.M_Num_Of_Nodes = num
        self.M_Nodes = range(self.M_Num_Of_Nodes)
        self.M_Directed = directed
        # Using Dictionary Comprehension (字典推导式)
        self.M_Adj_List = {node: set() for node in self.M_Nodes}

    def Add_Edge(self, node_start, node_end, weight):
        # Add Element: Tuple[node_end,weight]
        # INTO Key:node_start 's Value(set)
        # list is NOT hashable that CAN't add in set
        self.M_Adj_List[node_start].add((node_end, weight))
        if not self.M_Directed:
            self.M_Adj_List[node_end].add((node_start, weight))

    def Print_Edge_List(self):
        print(self.M_Adj_List)



class GraphList:
    # constructor
    def __init__(self, num_of_node: int, directed=True):
        self.M_Num_Of_Node = num_of_node
        self.M_Directed = directed
        # different representation of a graph
        self.M_List_Of_edges = []

    # Add edge to a graph
    def Add_edge(self, node_start, node_end, weight=1):
        # Add the edge from node_start to node_end
        self.M_List_Of_edges.append([node_start, node_end, weight])
        # If a graph is undirected, add the same edge
        # but also in the opposite direction
        if not self.M_Directed:
            self.M_List_Of_edges.append([node_end, node_start, weight])

    # Print the edge list of graph
    def Print_Edge_List(self):
        print("The edge list of graph:\n[Start, End, weight]")
        for x in self.M_List_Of_edges:
            print(x)

    # A utility function to find set of an element i
    # (truly uses path compression technique)
    def Find(self, parent, i):
        if parent[i] != i:
            # Reassignment of node's parent
            # to root node as
            # path compression requires
            parent[i] = self.Find(parent, parent[i])
        return parent[i]

    # A function that does union of two sets of x and y
    # (uses union by rank)
    def Union(self, parent, rank, x, y):
        # Attach smaller rank tree under root of
        # high rank tree(Union by Rank)
        if rank[x] < rank[y]:
            parent[x] = y
        elif rank[x] > rank[y]:
            parent[y] = x
        # If ranks are same,then make one as root
        # and increment its rank by one
        else:
            parent[y] = x
            rank[x] += 1

    # The main function to construct MsT
    # using kruskal's algorithm
    def KruskalMsT(self):
        # This will store the resultant MST
        result = []
        # An index variable,used for sorted edges
        i = 0
        # An index variable,used for result[]
        e = 0
        # Sort all the edges in
        # non-decreasing order of their
        # weight
        self.M_List_Of_edges = sorted(self.M_List_Of_edges,key = lambda item: item[2])
        parent = []
        rank = []
        for node in range(self.M_Num_Of_Node):
            parent.append(node)
            rank.append(0)
        while e < self.M_Num_Of_Node - 1:
            u,v,w = self.M_List_Of_edges[i]
            i += 1
            x = self.Find(parent, u)
            y = self.Find(parent, v)
            if x != y:
                e += 1
                result.append([u,v,w])
                self.Union(parent, rank, x, y)
        minimumCost = 0
        print("Edge in the constructed MST:")
        for u,v,weight in result:
            minimumCost += weight
            print("%d -- %d == %d" % (u, v, weight))
        print("Minimum Spanning Tree", minimumCost)




import sys

class GraphMatrix:
    def __init__(self, num_of_nodes, directed=True):
        """
        传入节点数、默认有向图
        初始化二维矩阵作为邻接矩阵
        :param num_of_nodes:
        :param directed:
        """
        self.M_Num_Of_Nodes = num_of_nodes
        self.M_Directed = directed
        self.M_Adj_MaTrix = [[0 for columns in range(self.M_Num_Of_Nodes)],
                             [0 for rows in range(self.M_Num_Of_Nodes)]]

    def Add_edges(self, node_start, node_end, weight=1):
        self.M_Adj_MaTrix[node_start][node_end] = weight
        if not self.M_Directed:
            self.M_Adj_MaTrix[node_end][node_start] = weight

    def Print_Adj_Matrix(self):
        print(self.M_Adj_MaTrix)


    def printMST(self, parent):
        """
        打印最小生成树的函数。
        A utility function to print the constructed MST stored in parent[]
        :param parent:
        :return:
        """
        print("Edge \t Weight")
        for i in range(1, self.M_Num_Of_Nodes):
            print(parent[i], "-", i, "\t", self.M_Adj_MaTrix[i][parent[i]])



    def minKey(self, key, mstSet):
        """
        用于从尚未包含在MST中的顶点集合中找到具有最小距离值的顶点。
        :param key:
        :param mstSet:
        :return:
        """
        # 初始化最小值
        minValue = sys.maxsize
        min_index = 0
        for v in range(self.M_Num_Of_Nodes):
            if key[v] < minValue and not mstSet[v]:
                minValue = key[v]
                min_index = v
        return min_index

    def primMST(self):
        """
        构造并打印邻接矩阵表示的图的MST
        :return:
        """
        # 初始化key列表
        key = [sys.maxsize] * self.M_Num_Of_Nodes
        parent = [None]*self.M_Num_Of_Nodes   # 存储构造的MST的数组
        parent[0] = -1  # 初始化parent列表
        # 选第一个顶点
        key[0] = 0
        mstSet = [False] * self.M_Num_Of_Nodes
        # 从尚未处理的顶点集合中选择距离最小的顶点
        for count in range(self.M_Num_Of_Nodes):
            # 取u为最小值位置
            u = self.minKey(key, mstSet)
            # 在MST中放置最小距离顶点，通过标记为true实现
            mstSet[u] = True
            # 只有当当前距离大于新距离且该顶点不在最短路径树中时，才更新所选顶点的相邻顶点的dist值
            for v in range(self.M_Num_Of_Nodes):
                # 只有当图[u][v]小于key[v]时，才会更新key
                # 图[u][v]对于m的相邻顶点是非零的
                if 0 < self.M_Adj_MaTrix[u][v] < key[v] and not mstSet[v]:
                    key[v] = self.M_Adj_MaTrix[u][v]
                    parent[v] = u
            # 结束本轮遍历
        # 则 parent 列表存储了最短路径所在节点
        self.printMST(parent)


    def minDistance(self, dist: list, sptset: list):
        """
        返回最小值位置；
        对dist中值寻找最小，并对照sptset筛选未选取项。
        :param dist:
        :param sptset:
        :return min_index:
        """
        min = 1e7
        for v in range(self.M_Num_Of_Nodes):
            if dist[v] < min and sptset[v] is False:
                min = dist[v]
                min_index = v
        return min_index

    def dijkstra(self,src):
        """
        使用dijkstra算法实现最小生成树
        :param src:
        :return:
        """
        dist = [1e7] * self.M_Num_Of_Nodes
        dist[src] = 0
        sptSet = [False] * self.M_Num_Of_Nodes
        for count in range(self.M_Num_Of_Nodes):
            u = self.minDistance(dist,sptSet)
            sptSet[u] = True
            for v in range(self.M_Num_Of_Nodes):
                if ((self.M_Adj_MaTrix[u][v] > 0) and (sptSet[v] is False) and (dist[v] > (dist[u]+self.M_Adj_MaTrix[u][v]))):
                    dist[v] = dist[u]+self.M_Adj_MaTrix[u][v]
        self.Print_Adj_Matrix(dist)





g = GraphList(4)

g.Add_edge(0,1,10)
g.Add_edge(0,2,6)
g.Add_edge(0,3,5)
g.Add_edge(1,3,15)
g.Add_edge(2,3,4)

g.KruskalMsT()






graphBackClass = GraphMatrix(5)
graphBackClass.M_Adj_MaTrix = [[0, 2, 0, 6, 0],
                               [2, 0, 3, 8, 5],
                               [0, 3, 0, 0, 7],
                               [6, 8, 0, 0, 9],
                               [0, 5, 7, 9, 0]]
graphBackClass.Print_Adj_Matrix()
graphBackClass.primMST()

gp = GraphMatrix(9)
gp.M_List_Of_edges = [[ 0 , 0.3,  1 ,  0 ,  0 , 0.5,  0 ,  0 ],
                      [0.3,  0 ,  1 , 0.8, 0.7,  0 ,  0 ,  0 ],
                      [ 1 ,  1 ,  0 ,  0 , 0.5,  2 ,  0 ,  0 ],
                      [ 0 , 0.8,  0 ,  0 ,  2 ,  0 ,  0 ,  3 ],
                      [ 0 , 0.7, 0.5,  2 ,  0 ,  1 , 2.5, 0.4],
                      [0.5,  0 ,  2 ,  0 ,  1 ,  0 ,  3 ,  0 ],
                      [ 0 ,  0 ,  0 ,  0 , 2.5,  3 ,  0 , 1.5],
                      [ 0 ,  0 ,  0 ,  3 , 0.4,  0 , 1.5,  0 ]]
gp.dijkstra(0)


graphOnClass1106 = GraphDict(5)
graphOnClass1106.Add_Edge(0, 0, 25)
graphOnClass1106.Add_Edge(0, 1, 5)
graphOnClass1106.Add_Edge(0, 2, 3)
graphOnClass1106.Add_Edge(1, 3, 1)
graphOnClass1106.Add_Edge(1, 4, 15)
graphOnClass1106.Add_Edge(4, 2, 7)
graphOnClass1106.Add_Edge(4, 3, 11)

graphOnClass1106.Print_Edge_List()





